package com.zhugang.week03;

import java.util.Stack;

/**
 * @program algorithms
 * @description: trap
 * @author: chanzhugang
 * @create: 2022/06/14 10:43
 */
public class Trap2 {

    /**
     * 42. 接雨水
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        /**
         * 每个柱子的盛水量 = min(左侧最高柱子，右侧最高柱子) - 当前柱子高度
         */
        int n = height.length;
        int res = 0;
        for (int i = 1; i < n - 1; i++) {
            int lh = 0;
            for (int j = 0; j < i; j++) {
                // 左侧最高柱子
                if (height[j] > lh) lh = height[j];
            }
            int rh = 0;
            for (int j = i + 1; j < n; j++) {
                // 右侧最高柱子
                if (height[j] > rh) rh = height[j];
            }
            int carry = Math.min(lh, rh) - height[i];
            if (carry < 0) carry = 0;
            res += carry;
        }
        return res;
    }

    public int trap2(int[] height) {
        /**
         * 前缀、后缀统计法,
         */
        // 前缀max
        int n = height.length;
        int max = 0;
        // 存的都是左侧最大值
        int[] leftMax = new int[n];
        for (int i = 0; i < n; i++) {
            leftMax[i] = Math.max(max, height[i]);
            max = leftMax[i];
        }
        // 后缀max：存的是右侧最大值
        int[] rightMax = new int[n];
        max = 0;
        for (int i = n - 1; i >= 0; i--) {
            rightMax[i] = Math.max(max, height[i]);
            max = rightMax[i];
        }
        int res = 0;
        for (int i = 1; i < n - 1; i++) {
            int carry = Math.min(leftMax[i], rightMax[i]) - height[i];
            res += carry;
        }
        return res;
    }

    public int trap3(int[] height) {
        /**
         * 单调栈解法： 画图理解，形成凹槽
         */
        int n = height.length;
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (stack.isEmpty()) {
                // 栈存下标
                stack.push(i);
                continue;
            }
            while (!stack.isEmpty()) {
                Integer top = stack.peek();
                if (height[top] >= height[i]) {
                    // 单调入栈
                    stack.push(i);
                    break;
                } else {
                    // 找到凹槽
                    top = stack.pop();
                    if (stack.isEmpty()) {
                        stack.push(i);
                        break;
                    }
                    Integer left = stack.peek();
                    int h = Math.min(height[left], height[i]) - height[top];
                    int w = i - left - 1;
                    res += h * w;
                }

            }
        }
        return res;
    }

    public int trap4(int[] height) {
        /**
         * 进一步优化代码
         */
        int n = height.length;
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (stack.isEmpty() || height[i] <= height[stack.peek()]) {
                // 单调入栈
                stack.push(i);
                continue;
            }
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int midHeight = height[stack.pop()];
                if (stack.isEmpty()) {
                    break;
                }
                int h = Math.min(height[i], height[stack.peek()]) - midHeight;
                int w = i - stack.peek() - 1;
                res += w * h;

            }
            stack.push(i);
        }
        return res;
    }


}